package com.itheima.day05.myquitesort.test1;

public class Test {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        printArray(arr);
        fasSortArray(arr,0,arr.length-1);
        printArray(arr);
    }


    // 快速排序
    public static void fasSortArray(int[] arr,int left, int rigth){
        if(rigth < left){
            return;
        }
        int left0 = left; // 左边
        int rigth0 = rigth; // 右边
        int baseNumber = arr[left0]; // 基数

            while(left != rigth){
                // 比较右边
                while(arr[rigth] >= baseNumber && rigth > left){
                    rigth--;
                }
                // 比较左边
                while(arr[left] <= baseNumber && left < rigth){
                    left++;
                }
                // 两边值互换
                int tamp = arr[left];
                arr[left] = arr[rigth];
                arr[rigth] = tamp;
            }
            int tamp = arr[left0];
            arr[left0] = arr[left];
            arr[left] = tamp;

            fasSortArray(arr,left0,left-1);
            fasSortArray(arr,left + 1,rigth0);
    }
    // 快速排序简写版
    public static int[] fasSortArrayTest(int[] arr,int left, int rigth){
        int left0 = left; // 左边
        int rigth0 = rigth; // 右边
        int baseNumber = arr[left0]; // 基数

        while(left != rigth){
            // 比较右边
            while(arr[rigth] >= baseNumber && rigth > left){
                rigth--;
            }
            // 比较左边
            while(arr[left] <= baseNumber && left < rigth){
                left++;
            }
            // 两边值互换
            int tamp = arr[left];
            arr[left] = arr[rigth];
            arr[rigth] = tamp;
        }
        arr[left0] = arr[left0] ^ arr[left];
        arr[left] = arr[left0] ^ arr[left];
        arr[left0] = arr[left0] ^ arr[left];
        return arr;
    }

    // 打印数组
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.print(arr[arr.length - 1]);
        System.out.println("]");
    }
}


